package A一周刷爆LeetCode.B基础提升.CKMP与Manacher算法;

/**
 * @author wei.zhao
 * @description: Manacher原始写法
 * @date 2022年09月28日 14:39
 */
public class Code02_Manacher原始写法 {

    public static void main(String[] args) {
        String str1 = "abc1234321ab";
        System.out.println(maxLcpsLength(str1));
    }

    public static int maxLcpsLength(String str) {
        if (null == str || str.length() == 0) {
            return 0;
        }
        char[] chars = manacherString(str);
        // 回文半径数组
        int[] arr = new int[chars.length];
        // 所扩到最右位置时的中心点
        int C = -1;
        // 所扩到最右位置
        int R = -1;
        for (int i = 0; i < chars.length; i++) {
            int r = 1;
            if (i >= R) {
                // 当前来到的位置不在所扩到的最右位置里，暴力阔
                while (i - r >= 0 && i + r < chars.length && chars[i - r] == chars[i + r]) {
                    r++;
                }
                if (i + r - 1 > R) {
                    R = i + r - 1;
                    C = i;
                }
                arr[i] = r;
            } else {
                // 当前来到的位置在所扩到的最右位置里
                // i关于C的对称点
                int i2 = 2 * C - i;
                if (i2 - arr[i2] + 1 > C - arr[C] + 1) {
                    // 对称点的回文部分在C的左回文里，当前点与对称点回文一致
                    arr[i++] = arr[i2];
                } else if (i2 - arr[i2] + 1 < C - arr[C] + 1) {
                    // 对成点的回文部分不在C左回文里，当前点回文半径是到右边界距离
                    arr[i++] = R - i + 1;
                } else {
                    // 对成点的左回文与C的左回文重叠，至少是到R的距离，后面暴力阔
                    r = R - i + 1;
                    while (i - r >= 0 && i + r < chars.length && chars[i - r] == chars[i + r]) {
                        r++;
                    }
                    if (i + r - 1 > R) {
                        R = i + r - 1;
                        C = i;
                    }
                    arr[i] = r;
                }
            }
        }
        int result = 0;
        for (int i : arr) {
            if (i > result) {
                result = i-1;
            }
        }
        return result;
    }

    /**
     * 字符间加'#'，处理成特殊字符数组
     */
    public static char[] manacherString(String str) {
        char[] chars = new char[2 * str.length() + 1];
        for (int i = 0; i < chars.length; i++) {
            if (i % 2 == 0) {
                chars[i] = '#';
            } else {
                chars[i] = str.charAt(i / 2);
            }
        }
        return chars;
    }

}
